package leetcode.editor.cn.dsa10_recursion;
//经典汉诺塔问题

import java.util.ArrayList;
import java.util.List;

public class HanotaLcc0806_1 {
    public static void main(String[] args) {
        Solution solution = new HanotaLcc0806_1().new Solution();
        List<Integer> a = new ArrayList<>();
        a.add(2); a.add(1); a.add(0);
        List<Integer> c = new ArrayList<>();
        solution.hanota(a, new ArrayList<>(), c);
        System.out.println(c); // [2, 1, 0]
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
            movePlate(A.size(), A, B, C);
        }

        /**
         * @param size 需要移动盘子的数量
         * @param start 起始柱子
         * @param auxiliary 辅助柱子
         * @param target 目标柱子
         */
        private void movePlate (int size, List<Integer> start, List<Integer> auxiliary, List<Integer> target) {
            // 结束条件：只剩一个盘子时，直接从第一个柱子移动到第三个柱子即可
            if (size == 1) {
                target.add(start.remove(start.size()-1));
                return;
            }
            // 函数主功能：移动n-1个盘子，移动第n个盘子，移动n-1个盘子
            // 等价关系式 f(n,A,B,C)=f(n-1,A,C,B)+M(A,C)+f(n-1,B,A,C)
            // 将n-1个盘子，从第一个柱子移动到第二个柱子
            movePlate(size-1, start, target, auxiliary);
            // 将第n个盘子，从第一个柱子移动到第三个柱子
            target.add(start.remove(start.size() - 1));
            // 再将n-1个盘子，从第二个柱子移动到第三个柱子
            movePlate(size-1, auxiliary, start, target);
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)
}